package com.sx.sx1.lintcode.day717;
import java.util.*;
public class LC316 {

    static class Solution {
        /**
         * @param num:    a array
         * @param target: a num
         * @return: return all combinations
         * we will sort your return value in output
         */

        public List<Integer> combinationSet(List<Integer> num, int target) {
            List<Integer> ans = new ArrayList<>();
            dfs(num,target,ans,-1);
            return ans;
        }

        public void dfs(List<Integer> ll,int target,List<Integer> ans,int parent){
            if(parent!=-1 && parent<target){
                ans.add(parent);
            }

            if(parent ==0 || parent>= target) return;
            if(parent ==-1) parent =0;
            for (int i = 0; i <ll.size() ; i++) {
                int cur =parent*10+ll.get(i);
                dfs(ll,target,ans,cur);
            }
        }

    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.combinationSet(new ArrayList<>(Arrays.asList(0,1,2,3)),30));
    }



    static class Solution1 {
        /**
         * @param num: a array
         * @param target: a num
         * @return: return all combinations
         *          we will sort your return value in output
         */
        public List<Integer> combinationSet(List<Integer> num, int target) {
            // write your code here
            Set<Integer> resultset = new HashSet<>();  // use set to take care of repeated elements
            if (num == null || num.size() == 0) return new ArrayList<>();
            // root node
            for (int i = 0; i < num.size(); i++) {
                dfs(num, target, num.get(i), resultset);
            }
            return new ArrayList<>(resultset);
        }

        private void dfs(List<Integer> num, int target, int currVal, Set<Integer> resultset) {
            if (currVal >= target) return;
            // any child node with currVal < target, add to result
            resultset.add(currVal);
            for (int i = 0; i < num.size(); i++) {
                if (currVal == 0) continue;
                dfs(num, target, 10 * currVal + num.get(i), resultset);
            }
        }
    }
// Note to self: each element can be used infinite number of times, but dfs() exits when currVal exceeds target.
// i.e. when target = 500 and currVal = 1111, we stop going down the tree
}



/*
LintCode-Logo
学习
刷题
题集
群组

内推
VIP
CAT
其他...
搜索题目、标签、题集
邀请有礼
中文
您上个月的刷题报告已生成，点击查看
avatar
316 · 组合集
算法
中等
通过率
49%
题目
题解6
笔记
讨论7
排名
记录
描述
给一个数组，在所有的排列组合中，找出小于给定数值的数。

【附答案】花高价求来的OpenAI题库，仅限前50份！

微信加sunny【jiuzhang1104】备注【AI】即可领取


1
<
=
�
�
�
(
�
�
�
)
<
=
10
1<=len(num)<=10
0
<
=
�
�
�
[
�
]
<
=
9
0<=num[i]<=9
�
�
�
�
�
�
<
=
1
0
6
target<=10
6

忽略返回ans的数组顺序
样例
输入 : num = [0,1,2,3] target = 30
输出: ans = [0,1,10,11,12,13,2,20,21,22,23,3]
标签
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
105/2433
已开启智能提示
发起考试
30 分 00 秒
1234567891011
public class Solution {
    /**
     * @param num: a array
     * @param target: a num
     * @return: return all combinations
     *          we will sort your return value in output
     */
/*
public List<Integer> combinationSet(List<Integer> num, int target) {
        // write your code here
        }

        控制台
        历史提交

 */
